#include "deflate.h"

const char deflate_copyright[] =
  " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";

typedef enum {
  need_more,      /* block not completed, need more input or more output */
  block_done,     /* block flush performed */
  finish_started, /* finish started, need only more output at next deflate */
  finish_done     /* finish done, accept no more input or output */
} block_state;

typedef block_state( *compress_func ) OF( ( deflate_state *s, int flush ) );

local void fill_window    OF( ( deflate_state *s ) );
local block_state deflate_stored OF( ( deflate_state *s, int flush ) );
local block_state deflate_fast   OF( ( deflate_state *s, int flush ) );
#ifndef FASTEST
local block_state deflate_slow   OF( ( deflate_state *s, int flush ) );
#endif
local void lm_init        OF( ( deflate_state *s ) );
local void putShortMSB    OF( ( deflate_state *s, uInt b ) );
local void flush_pending  OF( ( z_streamp strm ) );
local int read_buf        OF( ( z_streamp strm, Bytef *buf, unsigned size ) );
#ifndef FASTEST
#ifdef ASMV
void match_init OF( ( void ) ); /* asm code initialization */
uInt longest_match  OF( ( deflate_state *s, IPos cur_match ) );
#else
local uInt longest_match  OF( ( deflate_state *s, IPos cur_match ) );
#endif
#endif
local uInt longest_match_fast OF( ( deflate_state *s, IPos cur_match ) );

#ifdef DEBUG
local  void check_match OF( ( deflate_state *s, IPos start, IPos match,
                              int length ) );
#endif

#define NIL 0

#ifndef TOO_FAR
#  define TOO_FAR 4096
#endif

#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
typedef struct config_s {
  ush good_length; /* reduce lazy search above this match length */
  ush max_lazy;    /* do not perform lazy search above this match length */
  ush nice_length; /* quit search above this match length */
  ush max_chain;
  compress_func func;
} config;

#ifdef FASTEST
local const config configuration_table[2] = {
  /*      good lazy nice chain */
  /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  /* 1 */ {4,    4,  8,    4, deflate_fast}
}; /* max speed, no lazy matches */
#else
local const config configuration_table[10] = {
  /*      good lazy nice chain */
  /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  /* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
  /* 2 */ {4,    5, 16,    8, deflate_fast},
  /* 3 */ {4,    6, 32,   32, deflate_fast},

  /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
  /* 5 */ {8,   16, 32,   32, deflate_slow},
  /* 6 */ {8,   16, 128, 128, deflate_slow},
  /* 7 */ {8,   32, 128, 256, deflate_slow},
  /* 8 */ {32, 128, 258, 1024, deflate_slow},
  /* 9 */ {32, 258, 258, 4096, deflate_slow}
}; /* max compression */
#endif


#define EQUAL 0

#ifndef NO_DUMMY_DECL
struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
#endif

#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)


#ifdef FASTEST
#define INSERT_STRING(s, str, match_head) \
  (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
   match_head = s->head[s->ins_h], \
   s->head[s->ins_h] = (Pos)(str))
#else
#define INSERT_STRING(s, str, match_head) \
  (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
   match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
   s->head[s->ins_h] = (Pos)(str))
#endif

#define CLEAR_HASH(s) \
  s->head[s->hash_size-1] = NIL; \
  zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));

int ZEXPORT deflateInit_( z_streamp strm, int level, const char * version, int stream_size ) {
  return deflateInit2_( strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
                        Z_DEFAULT_STRATEGY, version, stream_size );
}

int ZEXPORT deflateInit2_( z_streamp strm, int level, int method, int windowBits, int memLevel, int strategy,
                           const char * version, int stream_size ) {
  deflate_state *s;
  int wrap = 1;
  static const char my_version[] = ZLIB_VERSION;
  ushf *overlay;
  if( version == Z_NULL || version[0] != my_version[0] ||
      stream_size != sizeof( z_stream ) ) {
    return Z_VERSION_ERROR;
  }
  if( strm == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  strm->msg = Z_NULL;
  if( strm->zalloc == ( alloc_func )0 ) {
    strm->zalloc = zcalloc;
    strm->opaque = ( voidpf )0;
  }
  if( strm->zfree == ( free_func )0 ) {
    strm->zfree = zcfree;
  }
  #ifdef FASTEST
  if( level != 0 ) {
    level = 1;
  }
  #else
  if( level == Z_DEFAULT_COMPRESSION ) {
    level = 6;
  }
  #endif
  if( windowBits < 0 ) { /* suppress zlib wrapper */
    wrap = 0;
    windowBits = -windowBits;
  }
  #ifdef GZIP
  else if( windowBits > 15 ) {
    wrap = 2;       /* write gzip wrapper instead */
    windowBits -= 16;
  }
  #endif
  if( memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
      windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
      strategy < 0 || strategy > Z_FIXED ) {
    return Z_STREAM_ERROR;
  }
  if( windowBits == 8 ) {
    windowBits = 9;  /* until 256-byte window bug fixed */
  }
  s = ( deflate_state * ) ZALLOC( strm, 1, sizeof( deflate_state ) );
  if( s == Z_NULL ) {
    return Z_MEM_ERROR;
  }
  strm->state = ( struct internal_state FAR * )s;
  s->strm = strm;
  s->wrap = wrap;
  s->gzhead = Z_NULL;
  s->w_bits = windowBits;
  s->w_size = 1 << s->w_bits;
  s->w_mask = s->w_size - 1;
  s->hash_bits = memLevel + 7;
  s->hash_size = 1 << s->hash_bits;
  s->hash_mask = s->hash_size - 1;
  s->hash_shift = ( ( s->hash_bits + MIN_MATCH - 1 ) / MIN_MATCH );
  s->window = ( Bytef * ) ZALLOC( strm, s->w_size, 2 * sizeof( Byte ) );
  s->prev   = ( Posf * )  ZALLOC( strm, s->w_size, sizeof( Pos ) );
  s->head   = ( Posf * )  ZALLOC( strm, s->hash_size, sizeof( Pos ) );
  s->lit_bufsize = 1 << ( memLevel + 6 ); /* 16K elements by default */
  overlay = ( ushf * ) ZALLOC( strm, s->lit_bufsize, sizeof( ush ) + 2 );
  s->pending_buf = ( uchf * ) overlay;
  s->pending_buf_size = ( ulg )s->lit_bufsize * ( sizeof( ush ) + 2L );
  if( s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
      s->pending_buf == Z_NULL ) {
    s->status = FINISH_STATE;
    strm->msg = ( char* )ERR_MSG( Z_MEM_ERROR );
    deflateEnd( strm );
    return Z_MEM_ERROR;
  }
  s->d_buf = overlay + s->lit_bufsize / sizeof( ush );
  s->l_buf = s->pending_buf + ( 1 + sizeof( ush ) ) * s->lit_bufsize;
  s->level = level;
  s->strategy = strategy;
  s->method = ( Byte )method;
  return deflateReset( strm );
}

int ZEXPORT deflateSetDictionary( z_streamp strm, const Bytef * dictionary, uInt dictLength ) {
  deflate_state *s;
  uInt length = dictLength;
  uInt n;
  IPos hash_head = 0;
  if( strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
      strm->state->wrap == 2 ||
      ( strm->state->wrap == 1 && strm->state->status != INIT_STATE ) ) {
    return Z_STREAM_ERROR;
  }
  s = strm->state;
  if( s->wrap ) {
    strm->adler = adler32( strm->adler, dictionary, dictLength );
  }
  if( length < MIN_MATCH ) {
    return Z_OK;
  }
  if( length > MAX_DIST( s ) ) {
    length = MAX_DIST( s );
    dictionary += dictLength - length; /* use the tail of the dictionary */
  }
  zmemcpy( s->window, dictionary, length );
  s->strstart = length;
  s->block_start = ( long )length;
  s->ins_h = s->window[0];
  UPDATE_HASH( s, s->ins_h, s->window[1] );
  for( n = 0; n <= length - MIN_MATCH; n++ ) {
    INSERT_STRING( s, n, hash_head );
  }
  if( hash_head ) {
    hash_head = 0;  /* to make compiler happy */
  }
  return Z_OK;
}

int ZEXPORT deflateReset( z_streamp strm ) {
  deflate_state *s;
  if( strm == Z_NULL || strm->state == Z_NULL ||
      strm->zalloc == ( alloc_func )0 || strm->zfree == ( free_func )0 ) {
    return Z_STREAM_ERROR;
  }
  strm->total_in = strm->total_out = 0;
  strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
  strm->data_type = Z_UNKNOWN;
  s = ( deflate_state * )strm->state;
  s->pending = 0;
  s->pending_out = s->pending_buf;
  if( s->wrap < 0 ) {
    s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
  }
  s->status = s->wrap ? INIT_STATE : BUSY_STATE;
  strm->adler =
    #ifdef GZIP
    s->wrap == 2 ? crc32( 0L, Z_NULL, 0 ) :
    #endif
    adler32( 0L, Z_NULL, 0 );
  s->last_flush = Z_NO_FLUSH;
  _tr_init( s );
  lm_init( s );
  return Z_OK;
}

int ZEXPORT deflateSetHeader( z_streamp strm, gz_headerp head ) {
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  if( strm->state->wrap != 2 ) {
    return Z_STREAM_ERROR;
  }
  strm->state->gzhead = head;
  return Z_OK;
}

int ZEXPORT deflatePrime( z_streamp strm, int bits, int value ) {
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  strm->state->bi_valid = bits;
  strm->state->bi_buf = ( ush )( value & ( ( 1 << bits ) - 1 ) );
  return Z_OK;
}

int ZEXPORT deflateParams( z_streamp strm, int level, int strategy ) {
  deflate_state *s;
  compress_func func;
  int err = Z_OK;
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  s = strm->state;
  #ifdef FASTEST
  if( level != 0 ) {
    level = 1;
  }
  #else
  if( level == Z_DEFAULT_COMPRESSION ) {
    level = 6;
  }
  #endif
  if( level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED ) {
    return Z_STREAM_ERROR;
  }
  func = configuration_table[s->level].func;
  if( func != configuration_table[level].func && strm->total_in != 0 ) {
    err = deflate( strm, Z_PARTIAL_FLUSH );
  }
  if( s->level != level ) {
    s->level = level;
    s->max_lazy_match   = configuration_table[level].max_lazy;
    s->good_match       = configuration_table[level].good_length;
    s->nice_match       = configuration_table[level].nice_length;
    s->max_chain_length = configuration_table[level].max_chain;
  }
  s->strategy = strategy;
  return err;
}

int ZEXPORT deflateTune( z_streamp strm, int good_length, int max_lazy, int nice_length, int max_chain ) {
  deflate_state *s;
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  s = strm->state;
  s->good_match = good_length;
  s->max_lazy_match = max_lazy;
  s->nice_match = nice_length;
  s->max_chain_length = max_chain;
  return Z_OK;
}

uLong ZEXPORT deflateBound( z_streamp strm, uLong sourceLen ) {
  deflate_state *s;
  uLong destLen;
  destLen = sourceLen +
            ( ( sourceLen + 7 ) >> 3 ) + ( ( sourceLen + 63 ) >> 6 ) + 11;
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return destLen;
  }
  s = strm->state;
  if( s->w_bits != 15 || s->hash_bits != 8 + 7 ) {
    return destLen;
  }
  return compressBound( sourceLen );
}

local void putShortMSB( deflate_state *s, uInt b ) {
  put_byte( s, ( Byte )( b >> 8 ) );
  put_byte( s, ( Byte )( b & 0xff ) );
}

local void flush_pending( z_streamp strm ) {
  unsigned len = strm->state->pending;
  if( len > strm->avail_out ) {
    len = strm->avail_out;
  }
  if( len == 0 ) {
    return;
  }
  zmemcpy( strm->next_out, strm->state->pending_out, len );
  strm->next_out  += len;
  strm->state->pending_out  += len;
  strm->total_out += len;
  strm->avail_out  -= len;
  strm->state->pending -= len;
  if( strm->state->pending == 0 ) {
    strm->state->pending_out = strm->state->pending_buf;
  }
}

int ZEXPORT deflate( z_streamp strm, int flush ) {
  int old_flush;
  deflate_state *s;
  if( strm == Z_NULL || strm->state == Z_NULL ||
      flush > Z_FINISH || flush < 0 ) {
    return Z_STREAM_ERROR;
  }
  s = strm->state;
  if( strm->next_out == Z_NULL ||
      ( strm->next_in == Z_NULL && strm->avail_in != 0 ) ||
      ( s->status == FINISH_STATE && flush != Z_FINISH ) ) {
    ERR_RETURN( strm, Z_STREAM_ERROR );
  }
  if( strm->avail_out == 0 ) {
    ERR_RETURN( strm, Z_BUF_ERROR );
  }
  s->strm = strm;
  old_flush = s->last_flush;
  s->last_flush = flush;
  if( s->status == INIT_STATE ) {
    #ifdef GZIP
    if( s->wrap == 2 ) {
      strm->adler = crc32( 0L, Z_NULL, 0 );
      put_byte( s, 31 );
      put_byte( s, 139 );
      put_byte( s, 8 );
      if( s->gzhead == NULL ) {
        put_byte( s, 0 );
        put_byte( s, 0 );
        put_byte( s, 0 );
        put_byte( s, 0 );
        put_byte( s, 0 );
        put_byte( s, s->level == 9 ? 2 :
                  ( s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
                    4 : 0 ) );
        put_byte( s, OS_CODE );
        s->status = BUSY_STATE;
      } else {
        put_byte( s, ( s->gzhead->text ? 1 : 0 ) +
                  ( s->gzhead->hcrc ? 2 : 0 ) +
                  ( s->gzhead->extra == Z_NULL ? 0 : 4 ) +
                  ( s->gzhead->name == Z_NULL ? 0 : 8 ) +
                  ( s->gzhead->comment == Z_NULL ? 0 : 16 )
                );
        put_byte( s, ( Byte )( s->gzhead->time & 0xff ) );
        put_byte( s, ( Byte )( ( s->gzhead->time >> 8 ) & 0xff ) );
        put_byte( s, ( Byte )( ( s->gzhead->time >> 16 ) & 0xff ) );
        put_byte( s, ( Byte )( ( s->gzhead->time >> 24 ) & 0xff ) );
        put_byte( s, s->level == 9 ? 2 :
                  ( s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
                    4 : 0 ) );
        put_byte( s, s->gzhead->os & 0xff );
        if( s->gzhead->extra != NULL ) {
          put_byte( s, s->gzhead->extra_len & 0xff );
          put_byte( s, ( s->gzhead->extra_len >> 8 ) & 0xff );
        }
        if( s->gzhead->hcrc )
          strm->adler = crc32( strm->adler, s->pending_buf,
                               s->pending );
        s->gzindex = 0;
        s->status = EXTRA_STATE;
      }
    } else
    #endif
    {
      uInt header = ( Z_DEFLATED + ( ( s->w_bits - 8 ) << 4 ) ) << 8;
      uInt level_flags;
      if( s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ) {
        level_flags = 0;
      } else if( s->level < 6 ) {
        level_flags = 1;
      } else if( s->level == 6 ) {
        level_flags = 2;
      } else
      { level_flags = 3; }
      header |= ( level_flags << 6 );
      if( s->strstart != 0 ) {
        header |= PRESET_DICT;
      }
      header += 31 - ( header % 31 );
      s->status = BUSY_STATE;
      putShortMSB( s, header );
      if( s->strstart != 0 ) {
        putShortMSB( s, ( uInt )( strm->adler >> 16 ) );
        putShortMSB( s, ( uInt )( strm->adler & 0xffff ) );
      }
      strm->adler = adler32( 0L, Z_NULL, 0 );
    }
  }
  #ifdef GZIP
  if( s->status == EXTRA_STATE ) {
    if( s->gzhead->extra != NULL ) {
      uInt beg = s->pending;
      while( s->gzindex < ( s->gzhead->extra_len & 0xffff ) ) {
        if( s->pending == s->pending_buf_size ) {
          if( s->gzhead->hcrc && s->pending > beg )
            strm->adler = crc32( strm->adler, s->pending_buf + beg,
                                 s->pending - beg );
          flush_pending( strm );
          beg = s->pending;
          if( s->pending == s->pending_buf_size ) {
            break;
          }
        }
        put_byte( s, s->gzhead->extra[s->gzindex] );
        s->gzindex++;
      }
      if( s->gzhead->hcrc && s->pending > beg )
        strm->adler = crc32( strm->adler, s->pending_buf + beg,
                             s->pending - beg );
      if( s->gzindex == s->gzhead->extra_len ) {
        s->gzindex = 0;
        s->status = NAME_STATE;
      }
    } else
    { s->status = NAME_STATE; }
  }
  if( s->status == NAME_STATE ) {
    if( s->gzhead->name != NULL ) {
      uInt beg = s->pending;
      int val;
      do {
        if( s->pending == s->pending_buf_size ) {
          if( s->gzhead->hcrc && s->pending > beg )
            strm->adler = crc32( strm->adler, s->pending_buf + beg,
                                 s->pending - beg );
          flush_pending( strm );
          beg = s->pending;
          if( s->pending == s->pending_buf_size ) {
            val = 1;
            break;
          }
        }
        val = s->gzhead->name[s->gzindex++];
        put_byte( s, val );
      } while( val != 0 );
      if( s->gzhead->hcrc && s->pending > beg )
        strm->adler = crc32( strm->adler, s->pending_buf + beg,
                             s->pending - beg );
      if( val == 0 ) {
        s->gzindex = 0;
        s->status = COMMENT_STATE;
      }
    } else
    { s->status = COMMENT_STATE; }
  }
  if( s->status == COMMENT_STATE ) {
    if( s->gzhead->comment != NULL ) {
      uInt beg = s->pending;
      int val;
      do {
        if( s->pending == s->pending_buf_size ) {
          if( s->gzhead->hcrc && s->pending > beg )
            strm->adler = crc32( strm->adler, s->pending_buf + beg,
                                 s->pending - beg );
          flush_pending( strm );
          beg = s->pending;
          if( s->pending == s->pending_buf_size ) {
            val = 1;
            break;
          }
        }
        val = s->gzhead->comment[s->gzindex++];
        put_byte( s, val );
      } while( val != 0 );
      if( s->gzhead->hcrc && s->pending > beg )
        strm->adler = crc32( strm->adler, s->pending_buf + beg,
                             s->pending - beg );
      if( val == 0 ) {
        s->status = HCRC_STATE;
      }
    } else
    { s->status = HCRC_STATE; }
  }
  if( s->status == HCRC_STATE ) {
    if( s->gzhead->hcrc ) {
      if( s->pending + 2 > s->pending_buf_size ) {
        flush_pending( strm );
      }
      if( s->pending + 2 <= s->pending_buf_size ) {
        put_byte( s, ( Byte )( strm->adler & 0xff ) );
        put_byte( s, ( Byte )( ( strm->adler >> 8 ) & 0xff ) );
        strm->adler = crc32( 0L, Z_NULL, 0 );
        s->status = BUSY_STATE;
      }
    } else
    { s->status = BUSY_STATE; }
  }
  #endif
  if( s->pending != 0 ) {
    flush_pending( strm );
    if( strm->avail_out == 0 ) {
      s->last_flush = -1;
      return Z_OK;
    }
  } else if( strm->avail_in == 0 && flush <= old_flush &&
             flush != Z_FINISH ) {
    ERR_RETURN( strm, Z_BUF_ERROR );
  }
  if( s->status == FINISH_STATE && strm->avail_in != 0 ) {
    ERR_RETURN( strm, Z_BUF_ERROR );
  }
  if( strm->avail_in != 0 || s->lookahead != 0 ||
      ( flush != Z_NO_FLUSH && s->status != FINISH_STATE ) ) {
    block_state bstate;
    bstate = ( *( configuration_table[s->level].func ) )( s, flush );
    if( bstate == finish_started || bstate == finish_done ) {
      s->status = FINISH_STATE;
    }
    if( bstate == need_more || bstate == finish_started ) {
      if( strm->avail_out == 0 ) {
        s->last_flush = -1;
      }
      return Z_OK;
    }
    if( bstate == block_done ) {
      if( flush == Z_PARTIAL_FLUSH ) {
        _tr_align( s );
      } else {
        _tr_stored_block( s, ( char* )0, 0L, 0 );
        if( flush == Z_FULL_FLUSH ) {
          CLEAR_HASH( s );
        }
      }
      flush_pending( strm );
      if( strm->avail_out == 0 ) {
        s->last_flush = -1;
        return Z_OK;
      }
    }
  }
  Assert( strm->avail_out > 0, "bug2" );
  if( flush != Z_FINISH ) {
    return Z_OK;
  }
  if( s->wrap <= 0 ) {
    return Z_STREAM_END;
  }
  #ifdef GZIP
  if( s->wrap == 2 ) {
    put_byte( s, ( Byte )( strm->adler & 0xff ) );
    put_byte( s, ( Byte )( ( strm->adler >> 8 ) & 0xff ) );
    put_byte( s, ( Byte )( ( strm->adler >> 16 ) & 0xff ) );
    put_byte( s, ( Byte )( ( strm->adler >> 24 ) & 0xff ) );
    put_byte( s, ( Byte )( strm->total_in & 0xff ) );
    put_byte( s, ( Byte )( ( strm->total_in >> 8 ) & 0xff ) );
    put_byte( s, ( Byte )( ( strm->total_in >> 16 ) & 0xff ) );
    put_byte( s, ( Byte )( ( strm->total_in >> 24 ) & 0xff ) );
  } else
  #endif
  {
    putShortMSB( s, ( uInt )( strm->adler >> 16 ) );
    putShortMSB( s, ( uInt )( strm->adler & 0xffff ) );
  }
  flush_pending( strm );
  if( s->wrap > 0 ) {
    s->wrap = -s->wrap;
  }
  return s->pending != 0 ? Z_OK : Z_STREAM_END;
}

int ZEXPORT deflateEnd( z_streamp strm ) {
  int status;
  if( strm == Z_NULL || strm->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  status = strm->state->status;
  if( status != INIT_STATE &&
      status != EXTRA_STATE &&
      status != NAME_STATE &&
      status != COMMENT_STATE &&
      status != HCRC_STATE &&
      status != BUSY_STATE &&
      status != FINISH_STATE ) {
    return Z_STREAM_ERROR;
  }
  TRY_FREE( strm, strm->state->pending_buf );
  TRY_FREE( strm, strm->state->head );
  TRY_FREE( strm, strm->state->prev );
  TRY_FREE( strm, strm->state->window );
  ZFREE( strm, strm->state );
  strm->state = Z_NULL;
  return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
}

int ZEXPORT deflateCopy( z_streamp dest, z_streamp source ) {
  #ifdef MAXSEG_64K
  return Z_STREAM_ERROR;
  #else
  deflate_state *ds;
  deflate_state *ss;
  ushf *overlay;
  if( source == Z_NULL || dest == Z_NULL || source->state == Z_NULL ) {
    return Z_STREAM_ERROR;
  }
  ss = source->state;
  zmemcpy( dest, source, sizeof( z_stream ) );
  ds = ( deflate_state * ) ZALLOC( dest, 1, sizeof( deflate_state ) );
  if( ds == Z_NULL ) {
    return Z_MEM_ERROR;
  }
  dest->state = ( struct internal_state FAR * ) ds;
  zmemcpy( ds, ss, sizeof( deflate_state ) );
  ds->strm = dest;
  ds->window = ( Bytef * ) ZALLOC( dest, ds->w_size, 2 * sizeof( Byte ) );
  ds->prev   = ( Posf * )  ZALLOC( dest, ds->w_size, sizeof( Pos ) );
  ds->head   = ( Posf * )  ZALLOC( dest, ds->hash_size, sizeof( Pos ) );
  overlay = ( ushf * ) ZALLOC( dest, ds->lit_bufsize, sizeof( ush ) + 2 );
  ds->pending_buf = ( uchf * ) overlay;
  if( ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
      ds->pending_buf == Z_NULL ) {
    deflateEnd( dest );
    return Z_MEM_ERROR;
  }
  zmemcpy( ds->window, ss->window, ds->w_size * 2 * sizeof( Byte ) );
  zmemcpy( ds->prev, ss->prev, ds->w_size * sizeof( Pos ) );
  zmemcpy( ds->head, ss->head, ds->hash_size * sizeof( Pos ) );
  zmemcpy( ds->pending_buf, ss->pending_buf, ( uInt )ds->pending_buf_size );
  ds->pending_out = ds->pending_buf + ( ss->pending_out - ss->pending_buf );
  ds->d_buf = overlay + ds->lit_bufsize / sizeof( ush );
  ds->l_buf = ds->pending_buf + ( 1 + sizeof( ush ) ) * ds->lit_bufsize;
  ds->l_desc.dyn_tree = ds->dyn_ltree;
  ds->d_desc.dyn_tree = ds->dyn_dtree;
  ds->bl_desc.dyn_tree = ds->bl_tree;
  return Z_OK;
  #endif
}

local int read_buf( z_streamp strm, Bytef *buf, unsigned size ) {
  unsigned len = strm->avail_in;
  if( len > size ) {
    len = size;
  }
  if( len == 0 ) {
    return 0;
  }
  strm->avail_in  -= len;
  if( strm->state->wrap == 1 ) {
    strm->adler = adler32( strm->adler, strm->next_in, len );
  }
  #ifdef GZIP
  else if( strm->state->wrap == 2 ) {
    strm->adler = crc32( strm->adler, strm->next_in, len );
  }
  #endif
  zmemcpy( buf, strm->next_in, len );
  strm->next_in  += len;
  strm->total_in += len;
  return ( int )len;
}

local void lm_init( deflate_state *s ) {
  s->window_size = ( ulg )2L * s->w_size;
  CLEAR_HASH( s );
  s->max_lazy_match   = configuration_table[s->level].max_lazy;
  s->good_match       = configuration_table[s->level].good_length;
  s->nice_match       = configuration_table[s->level].nice_length;
  s->max_chain_length = configuration_table[s->level].max_chain;
  s->strstart = 0;
  s->block_start = 0L;
  s->lookahead = 0;
  s->match_length = s->prev_length = MIN_MATCH - 1;
  s->match_available = 0;
  s->ins_h = 0;
  #ifndef FASTEST
  #ifdef ASMV
  match_init();
  #endif
  #endif
}

#ifndef FASTEST
#ifndef ASMV
local uInt longest_match( deflate_state *s, IPos cur_match ) {
  unsigned chain_length = s->max_chain_length;
  register Bytef *scan = s->window + s->strstart;
  register Bytef *match;
  register int len;
  int best_len = s->prev_length;
  int nice_match = s->nice_match;
  IPos limit = s->strstart > ( IPos )MAX_DIST( s ) ?
               s->strstart - ( IPos )MAX_DIST( s ) : NIL;
  Posf *prev = s->prev;
  uInt wmask = s->w_mask;
  #ifdef UNALIGNED_OK
  register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
  register ush scan_start = *( ushf* )scan;
  register ush scan_end   = *( ushf* )( scan + best_len - 1 );
  #else
  register Bytef *strend = s->window + s->strstart + MAX_MATCH;
  register Byte scan_end1  = scan[best_len - 1];
  register Byte scan_end   = scan[best_len];
  #endif
  Assert( s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever" );
  if( s->prev_length >= s->good_match ) {
    chain_length >>= 2;
  }
  if( ( uInt )nice_match > s->lookahead ) {
    nice_match = s->lookahead;
  }
  Assert( ( ulg )s->strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead" );
  do {
    Assert( cur_match < s->strstart, "no future" );
    match = s->window + cur_match;
    #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
    if( *( ushf* )( match + best_len - 1 ) != scan_end ||
        *( ushf* )match != scan_start ) {
      continue;
    }
    Assert( scan[2] == match[2], "scan[2]?" );
    scan++, match++;
    do {
    } while( *( ushf* )( scan += 2 ) == *( ushf* )( match += 2 ) &&
             *( ushf* )( scan += 2 ) == *( ushf* )( match += 2 ) &&
             *( ushf* )( scan += 2 ) == *( ushf* )( match += 2 ) &&
             *( ushf* )( scan += 2 ) == *( ushf* )( match += 2 ) &&
             scan < strend );
    Assert( scan <= s->window + ( unsigned )( s->window_size - 1 ), "wild scan" );
    if( *scan == *match ) {
      scan++;
    }
    len = ( MAX_MATCH - 1 ) - ( int )( strend - scan );
    scan = strend - ( MAX_MATCH - 1 );
    #else
    if( match[best_len]   != scan_end  ||
        match[best_len - 1] != scan_end1 ||
        *match            != *scan     ||
        *++match          != scan[1] ) {
      continue;
    }
    scan += 2, match++;
    Assert( *scan == *match, "match[2]?" );
    do {
    } while( *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             scan < strend );
    Assert( scan <= s->window + ( unsigned )( s->window_size - 1 ), "wild scan" );
    len = MAX_MATCH - ( int )( strend - scan );
    scan = strend - MAX_MATCH;
    #endif
    if( len > best_len ) {
      s->match_start = cur_match;
      best_len = len;
      if( len >= nice_match ) {
        break;
      }
      #ifdef UNALIGNED_OK
      scan_end = *( ushf* )( scan + best_len - 1 );
      #else
      scan_end1  = scan[best_len - 1];
      scan_end   = scan[best_len];
      #endif
    }
  } while( ( cur_match = prev[cur_match & wmask] ) > limit
           && --chain_length != 0 );
  if( ( uInt )best_len <= s->lookahead ) {
    return ( uInt )best_len;
  }
  return s->lookahead;
}
#endif
#endif

local uInt longest_match_fast( deflate_state *s, IPos cur_match ) {
  register Bytef *scan = s->window + s->strstart;
  register Bytef *match;
  register int len;
  register Bytef *strend = s->window + s->strstart + MAX_MATCH;
  Assert( s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever" );
  Assert( ( ulg )s->strstart <= s->window_size - MIN_LOOKAHEAD, "need lookahead" );
  Assert( cur_match < s->strstart, "no future" );
  match = s->window + cur_match;
  if( match[0] != scan[0] || match[1] != scan[1] ) {
    return MIN_MATCH - 1;
  }
  scan += 2, match += 2;
  Assert( *scan == *match, "match[2]?" );
  do {
  } while( *++scan == *++match && *++scan == *++match &&
           *++scan == *++match && *++scan == *++match &&
           *++scan == *++match && *++scan == *++match &&
           *++scan == *++match && *++scan == *++match &&
           scan < strend );
  Assert( scan <= s->window + ( unsigned )( s->window_size - 1 ), "wild scan" );
  len = MAX_MATCH - ( int )( strend - scan );
  if( len < MIN_MATCH ) {
    return MIN_MATCH - 1;
  }
  s->match_start = cur_match;
  return ( uInt )len <= s->lookahead ? ( uInt )len : s->lookahead;
}

#ifdef DEBUG
local void check_match( deflate_state *s, IPos start, IPos match, int length ) {
  if( zmemcmp( s->window + match,
               s->window + start, length ) != EQUAL ) {
    fprintf( stderr, " start %u, match %u, length %d\n",
             start, match, length );
    do {
      fprintf( stderr, "%c%c", s->window[match++], s->window[start++] );
    } while( --length != 0 );
    z_error( "invalid match" );
  }
  if( z_verbose > 1 ) {
    fprintf( stderr, "\\[%d,%d]", start - match, length );
    do {
      putc( s->window[start++], stderr );
    } while( --length != 0 );
  }
}
#else
#  define check_match(s, start, match, length)
#endif

local void fill_window( deflate_state *s ) {
  register unsigned n, m;
  register Posf *p;
  unsigned more;
  uInt wsize = s->w_size;
  do {
    more = ( unsigned )( s->window_size - ( ulg )s->lookahead - ( ulg )s->strstart );
    if( sizeof( int ) <= 2 ) {
      if( more == 0 && s->strstart == 0 && s->lookahead == 0 ) {
        more = wsize;
      } else if( more == ( unsigned )( -1 ) ) {
        more--;
      }
    }
    if( s->strstart >= wsize + MAX_DIST( s ) ) {
      zmemcpy( s->window, s->window + wsize, ( unsigned )wsize );
      s->match_start -= wsize;
      s->strstart    -= wsize;
      s->block_start -= ( long ) wsize;
      n = s->hash_size;
      p = &s->head[n];
      do {
        m = *--p;
        *p = ( Pos )( m >= wsize ? m - wsize : NIL );
      } while( --n );
      n = wsize;
      #ifndef FASTEST
      p = &s->prev[n];
      do {
        m = *--p;
        *p = ( Pos )( m >= wsize ? m - wsize : NIL );
      } while( --n );
      #endif
      more += wsize;
    }
    if( s->strm->avail_in == 0 ) {
      return;
    }
    Assert( more >= 2, "more < 2" );
    n = read_buf( s->strm, s->window + s->strstart + s->lookahead, more );
    s->lookahead += n;
    if( s->lookahead >= MIN_MATCH ) {
      s->ins_h = s->window[s->strstart];
      UPDATE_HASH( s, s->ins_h, s->window[s->strstart + 1] );
      #if MIN_MATCH != 3
      Call UPDATE_HASH() MIN_MATCH - 3 more times
      #endif
    }
  } while( s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0 );
}

#define FLUSH_BLOCK_ONLY(s, eof) { \
    _tr_flush_block(s, (s->block_start >= 0L ? \
                        (charf *)&s->window[(unsigned)s->block_start] : \
                        (charf *)Z_NULL), \
                    (ulg)((long)s->strstart - s->block_start), \
                    (eof)); \
    s->block_start = s->strstart; \
    flush_pending(s->strm); \
    Tracev((stderr,"[FLUSH]")); \
  }

#define FLUSH_BLOCK(s, eof) { \
    FLUSH_BLOCK_ONLY(s, eof); \
    if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
  }

local block_state deflate_stored( deflate_state *s, int flush ) {
  ulg max_block_size = 0xffff;
  ulg max_start;
  if( max_block_size > s->pending_buf_size - 5 ) {
    max_block_size = s->pending_buf_size - 5;
  }
  for( ;; ) {
    if( s->lookahead <= 1 ) {
      Assert( s->strstart < s->w_size + MAX_DIST( s ) ||
              s->block_start >= ( long )s->w_size, "slide too late" );
      fill_window( s );
      if( s->lookahead == 0 && flush == Z_NO_FLUSH ) {
        return need_more;
      }
      if( s->lookahead == 0 ) {
        break;
      }
    }
    Assert( s->block_start >= 0L, "block gone" );
    s->strstart += s->lookahead;
    s->lookahead = 0;
    max_start = s->block_start + max_block_size;
    if( s->strstart == 0 || ( ulg )s->strstart >= max_start ) {
      s->lookahead = ( uInt )( s->strstart - max_start );
      s->strstart = ( uInt )max_start;
      FLUSH_BLOCK( s, 0 );
    }
    if( s->strstart - ( uInt )s->block_start >= MAX_DIST( s ) ) {
      FLUSH_BLOCK( s, 0 );
    }
  }
  FLUSH_BLOCK( s, flush == Z_FINISH );
  return flush == Z_FINISH ? finish_done : block_done;
}

local block_state deflate_fast( deflate_state *s, int flush ) {
  IPos hash_head = NIL;
  int bflush;
  for( ;; ) {
    if( s->lookahead < MIN_LOOKAHEAD ) {
      fill_window( s );
      if( s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH ) {
        return need_more;
      }
      if( s->lookahead == 0 ) {
        break;
      }
    }
    if( s->lookahead >= MIN_MATCH ) {
      INSERT_STRING( s, s->strstart, hash_head );
    }
    if( hash_head != NIL && s->strstart - hash_head <= MAX_DIST( s ) ) {
      #ifdef FASTEST
      if( ( s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE ) ||
          ( s->strategy == Z_RLE && s->strstart - hash_head == 1 ) ) {
        s->match_length = longest_match_fast( s, hash_head );
      }
      #else
      if( s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE ) {
        s->match_length = longest_match( s, hash_head );
      } else if( s->strategy == Z_RLE && s->strstart - hash_head == 1 ) {
        s->match_length = longest_match_fast( s, hash_head );
      }
      #endif
    }
    if( s->match_length >= MIN_MATCH ) {
      check_match( s, s->strstart, s->match_start, s->match_length );
      _tr_tally_dist( s, s->strstart - s->match_start,
                      s->match_length - MIN_MATCH, bflush );
      s->lookahead -= s->match_length;
      #ifndef FASTEST
      if( s->match_length <= s->max_insert_length &&
          s->lookahead >= MIN_MATCH ) {
        s->match_length--;
        do {
          s->strstart++;
          INSERT_STRING( s, s->strstart, hash_head );
        } while( --s->match_length != 0 );
        s->strstart++;
      } else
      #endif
      {
        s->strstart += s->match_length;
        s->match_length = 0;
        s->ins_h = s->window[s->strstart];
        UPDATE_HASH( s, s->ins_h, s->window[s->strstart + 1] );
        #if MIN_MATCH != 3
        Call UPDATE_HASH() MIN_MATCH - 3 more times
        #endif
      }
    } else {
      Tracevv( ( stderr, "%c", s->window[s->strstart] ) );
      _tr_tally_lit( s, s->window[s->strstart], bflush );
      s->lookahead--;
      s->strstart++;
    }
    if( bflush ) {
      FLUSH_BLOCK( s, 0 );
    }
  }
  FLUSH_BLOCK( s, flush == Z_FINISH );
  return flush == Z_FINISH ? finish_done : block_done;
}

#ifndef FASTEST
local block_state deflate_slow( deflate_state *s, int flush ) {
  IPos hash_head = NIL;
  int bflush;
  for( ;; ) {
    if( s->lookahead < MIN_LOOKAHEAD ) {
      fill_window( s );
      if( s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH ) {
        return need_more;
      }
      if( s->lookahead == 0 ) {
        break;
      }
    }
    if( s->lookahead >= MIN_MATCH ) {
      INSERT_STRING( s, s->strstart, hash_head );
    }
    s->prev_length = s->match_length, s->prev_match = s->match_start;
    s->match_length = MIN_MATCH - 1;
    if( hash_head != NIL && s->prev_length < s->max_lazy_match &&
        s->strstart - hash_head <= MAX_DIST( s ) ) {
      if( s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE ) {
        s->match_length = longest_match( s, hash_head );
      } else if( s->strategy == Z_RLE && s->strstart - hash_head == 1 ) {
        s->match_length = longest_match_fast( s, hash_head );
      }
      if( s->match_length <= 5 && ( s->strategy == Z_FILTERED
                                  #if TOO_FAR <= 32767
                                    || ( s->match_length == MIN_MATCH &&
                                         s->strstart - s->match_start > TOO_FAR )
                                  #endif
                                  ) ) {
        s->match_length = MIN_MATCH - 1;
      }
    }
    if( s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length ) {
      uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
      check_match( s, s->strstart - 1, s->prev_match, s->prev_length );
      _tr_tally_dist( s, s->strstart - 1 - s->prev_match,
                      s->prev_length - MIN_MATCH, bflush );
      s->lookahead -= s->prev_length - 1;
      s->prev_length -= 2;
      do {
        if( ++s->strstart <= max_insert ) {
          INSERT_STRING( s, s->strstart, hash_head );
        }
      } while( --s->prev_length != 0 );
      s->match_available = 0;
      s->match_length = MIN_MATCH - 1;
      s->strstart++;
      if( bflush ) {
        FLUSH_BLOCK( s, 0 );
      }
    } else if( s->match_available ) {
      Tracevv( ( stderr, "%c", s->window[s->strstart - 1] ) );
      _tr_tally_lit( s, s->window[s->strstart - 1], bflush );
      if( bflush ) {
        FLUSH_BLOCK_ONLY( s, 0 );
      }
      s->strstart++;
      s->lookahead--;
      if( s->strm->avail_out == 0 ) {
        return need_more;
      }
    } else {
      s->match_available = 1;
      s->strstart++;
      s->lookahead--;
    }
  }
  Assert( flush != Z_NO_FLUSH, "no flush?" );
  if( s->match_available ) {
    Tracevv( ( stderr, "%c", s->window[s->strstart - 1] ) );
    _tr_tally_lit( s, s->window[s->strstart - 1], bflush );
    s->match_available = 0;
  }
  FLUSH_BLOCK( s, flush == Z_FINISH );
  return flush == Z_FINISH ? finish_done : block_done;
}
#endif
